home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / prog / graph / match_test.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  942 b   |  60 lines
  1.  
  2. #include <LEDA/graph.h>
  3. #include <LEDA/graph_alg.h>
  4.  
  5.  
  6. edge_array<int>* W;
  7.  
  8. int EDGE_CMP(edge& e1, edge& e2)
  9. { return (*W[e1]-*W[e2]); }
  10.  
  11. main()
  12. {
  13.  
  14. GRAPH<int,int> G;
  15. list<node> A,B;
  16. edge e;
  17.  
  18. test_bigraph(G,A,B);
  19.  
  20.  
  21. edge_array<int> weight(G);
  22.  
  23. W = &weight;
  24.  
  25. if (Yes("random edge weights from [a..b] ? "))
  26.  { int a = read_int("a = ");
  27.    int b = read_int("b = ");
  28.    init_random();
  29.    forall_edges(e,G) G[e] = random(a,b);
  30.   }
  31. else
  32.  forall_edges(e,G)
  33.    { G.print_edge(e);
  34.      G[e] = read_int("  w = ");
  35.     }
  36.  
  37. forall_edges(e,G) weight[e] = G[e];
  38.  
  39. if (Yes("show graph ? ")) G.print();
  40.  
  41. list<edge> M1 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight);
  42.  
  43. forall(e,M1) { G.print_edge(e); newline; }
  44. newline;
  45.  
  46.  
  47. G.sort_edges(EDGE_CMP);
  48.  
  49. int i = 0;
  50. forall_edges(e,G) G[e] = weight[e] = i++;
  51. if (Yes("show graph? ")) G.print();
  52.  
  53. list<edge> M2 = MAX_WEIGHT_BIPARTITE_MATCHING(G,A,B,weight);
  54.  
  55. forall(e,M2) { G.print_edge(e); newline; }
  56. newline;
  57.  
  58. return 0;
  59. }
  60.